package nl.rug.jvleusen.datastructurelib.tree;

import nl.rug.jvleusen.datastructurelib.ITree;

/**
 * Implementation of {@link ITree} which enforces the rules of the Binary Search
 * Tree, which is that if you have a node with element E, the left subtree will
 * contain elements less than E, while the right subtree will contain elements
 * larger than E.
 *
 * @author Jeroen van Leusen
 */
public class BinaryTree<E extends Comparable<E>> implements ITree<E, BinaryTree.BinaryTreeNode<E>> {

    private BinaryTreeNode<E> root = null;
    private int size = 0;

    /**
     * Checks whether there is a node containing <tt>obj</tt> within this tree.
     *
     * @param obj The object to look for
     * @return Whether obj could be found.
     */
    public boolean contains(E obj) {
        return binarySearch(obj) != null;
    }

    /**
     * Attempts to insert a node with the given data according to the rules of
     * the binary search tree. If the node doesn't yet exist then a new node is
     * added.
     *
     * @param data element to insert.
     * @return Whether the element was successfully added.
     * @throws IllegalArgumentException If you try to insert null.
     */
    public boolean insert(E data) {
        if (root == null && data != null) {
            root = new BinaryTreeNode<E>(data);
            size++;
            return true;
        } else if (data == null) {
            throw new NullPointerException("BinaryTree does not accept NULL.");
        } else {
            return insert(root, data);
        }
    }

    private boolean insert(BinaryTreeNode<E> node, E data) {
        int compare = node.getData().compareTo(data);
        if (compare == 0) {
            //Stuff already in the tree, return false
            return false;
        } else {
            if (compare > 0) {
                BinaryTreeNode<E> left = node.getLeftNode();
                if (left == null) {
                    node.setLeftNode(new BinaryTreeNode<E>(data));
                } else {
                    return insert(left, data);
                }
            } else {
                //Check right
                BinaryTreeNode<E> right = node.getRightNode();
                if (right == null) {
                    node.setRightNode(new BinaryTreeNode<E>(data));
                } else {
                    return insert(right, data);
                }
            }
            size++;
            return true;
        }
    }

    /**
     * @return the number of elements in this tree.
     */
    public int size() {
        return size;
    }

    /**
     * {@inheritDoc}
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Attempts to remove the node with the given data.
     *
     * @param data element to look for.
     * @return Whether something was successfully removed.
     */
    public boolean remove(E data) {
        if (root == null) {
            return false;
        } else {
            boolean result;
            if (root.getData().compareTo(data) == 0) {
                BinaryTreeNode<E> holder = new BinaryTreeNode<E>(null);
                holder.setLeftNode(root);
                result = root.remove(data, holder);
                root = holder.getLeftNode();
            } else {
                result = root.remove(data, null);
            }

            if (result) {
                size--;
            }

            return result;
        }
    }

    /**
     * {@inheritDoc}
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

    /**
     * Preforms a binary search on this tree, returning the node if it finds a
     * node which {@code getData().compareTo(data) == 0} is true for. The
     * average complexity is {@code O(log(n))}, with a worst-case complexity of {@code O(n)}
     *
     * @param data The data to match to.
     * @return The node that contains the data which matches with the given
     * data, if it exists, returns null otherwise.
     * @throws IllegalArgumentException If you try to look for an element
     * containing a null element, because they cannot be compared.
     */
    public BinaryTreeNode<E> binarySearch(E data) {
        if (data == null) {
            throw new IllegalArgumentException("null is not a valid element.");
        }

        if (root == null) {
            return null;
        }

        BinaryTreeNode<E> node = root;
        int compare;
        while ((compare = node.getData().compareTo(data)) != 0) {
            if (compare > 0) {
                if (node.getLeftNode() != null) {
                    node = node.getLeftNode();
                } else {
                    return null;
                }
            } else {
                if (node.getRightNode() != null) {
                    node = node.getRightNode();
                } else {
                    return null;
                }
            }
        }

        return node;
    }

    /**
     * {@inheritDoc}
     */
    public int height() {
        if (root == null) {
            return -1;
        } else {
            return root.height();
        }
    }

    /**
     * Implementation of {@link TreeNode} that provides the required methods for {@link BinaryTree}
     */
    public static class BinaryTreeNode<E extends Comparable<E>> implements ITree.TreeNode<E> {

        private E data;
        private BinaryTreeNode<E> left;
        private BinaryTreeNode<E> right;

        protected BinaryTreeNode(E data) {
            this(data, null, null);
        }

        protected BinaryTreeNode(E data, BinaryTreeNode<E> left, BinaryTreeNode<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        /**
         * @return The left child.
         */
        public BinaryTreeNode<E> getLeftNode() {
            return left;
        }

        protected void setLeftNode(BinaryTreeNode<E> node) {
            this.left = node;
        }

        /**
         * @return The right child.
         */
        public BinaryTreeNode<E> getRightNode() {
            return right;
        }

        protected void setRightNode(BinaryTreeNode<E> node) {
            this.right = node;
        }

        protected boolean remove(E value, BinaryTreeNode<E> parent) {
            int compare = getData().compareTo(value);
            if (compare > 0) {
                if (left != null) {
                    return left.remove(value, this);
                } else {
                    return false;
                }
            } else if (compare < 0) {
                if (right != null) {
                    return right.remove(value, this);
                } else {
                    return false;
                }
            } else {
                if (left != null && right != null) {
                    this.data = right.minValue();
                    right.remove(this.data, this);
                } else if (parent.getLeftNode() == this) {
                    parent.left = (left != null) ? left : right;
                } else if (parent.getRightNode() == this) {
                    parent.right = (left != null) ? left : right;
                }
                return true;
            }
        }

        /**
         * @return The minimum value of the subtree spanned by this node.
         */
        public E minValue() {
            if (left == null) {
                return data;
            } else {
                return left.minValue();
            }
        }

        /**
         * {@inheritDoc}
         */
        public E getData() {
            return data;
        }

        /**
         * {@inheritDoc}
         */
        public int height() {
            int leftheight = (left == null) ? 0 : left.height();
            int rightheight = (right == null) ? 0 : right.height();
            return Math.max(leftheight, rightheight) + 1;
        }

        /**
         * {@inheritDoc}
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }
    }
}
